Day 09: Sort(3) - Merge Sort & Quick Sort - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

第 12 屆 iThome 鐵人賽

DAY 9

0

Software Development

你總是躲不掉的，不如放膽面對 LeetCode 吧！系列第 9 篇

Day 09: Sort(3) - Merge Sort & Quick Sort

12th鐵人賽

維特的兩條腿

團隊Outcome First

2020-09-22 22:38:04

5227 瀏覽

分享至

Merge Sort

簡單來說，將 Array 或是 Linked List 分割成幾乎等長的兩個串列，持續分割直到無法再分割為止。接著兩個兩個比較大小後合併成有排序的串列，持續合併直到只剩下一個串列，就完成了。

# 一開始
76 61 18 23 98 12 34 21 13 45
# 持續分割
76   61   18   23   98   12   34   21   13   45
# 開始比較與合併
# 第一回合
61 76    18 23    12 98    21 34    13 45
# 第二回合
18 23 61 76    12 21 34 98    13 45
# 第三回合
12 18 21 23 34 61 76 98    13 45
# 第四回合
12 13 18 21 23 34 45 61 76 98
# 排列結束

其背後的演算法可以歸類在：Divide and Conquer（分治法）。將複雜的問題分成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。

用 `Array` 實作

`JS`

/**
 * @param {number[]} arr
 * @param {number} arrStartIndex
 * @param {number} middleIndex
 * @param {number} arrEndIndex
 */
const merge = (arr, arrStartIndex, middleIndex, arrEndIndex) => {
  // 計算左右兩陣列的長度
  const leftArrLength = middleIndex - arrStartIndex + 1;
  const rightArrLength = arrEndIndex - middleIndex;

  // 製作左右兩陣列
  let LeftArr = new Array(leftArrLength);
  let RightArr = new Array(rightArrLength);

  // 將資料放入左右兩陣列
  for (let i = 0; i < leftArrLength; i++) {
    // 從 arrStarIndex 開始
    LeftArr[i] = arr[arrStartIndex + i];
  }

  for (let j = 0; j < rightArrLength; j++) {
    // 從 middleIndex 開始
    RightArr[j] = arr[middleIndex + 1 + j];
  }

  // 接著要開始遍歷左右陣列準備合併，於是要先建立兩個陣列的 index
  let leftArrIndex = 0, rightArrIndex = 0;
  // 合併後的大陣列 index
  let mergedArrIndex = arrStartIndex;

  while (leftArrIndex < leftArrLength && rightArrIndex < rightArrLength) {
    // 比較左右兩陣列的數值，數值小的放入合併後的陣列
    if (LeftArr[leftArrIndex] <= RightArr[rightArrIndex]) {
      arr[mergedArrIndex] = LeftArr[leftArrIndex];
      leftArrIndex++;
    } else {
      arr[mergedArrIndex] = RightArr[rightArrIndex];
      rightArrIndex++;
    }

    mergedArrIndex++;
  }

  // 將剩餘的數值放入合併後的陣列，剩餘數值會將大於合併後的陣列內的任一元素
  while (leftArrIndex < leftArrLength) {
    arr[mergedArrIndex] = LeftArr[leftArrIndex];
    leftArrIndex++;
    mergedArrIndex++;
  }

  // 將剩餘的數值放入合併後的陣列，剩餘數值會將大於合併後的陣列內的任一元素
  while (rightArrIndex < rightArrLength) {
    arr[mergedArrIndex] = RightArr[rightArrIndex];
    rightArrIndex++;
    mergedArrIndex++;
  }
};

/**
 * @param {number[]} arr
 * @param {number} arrStartIndex
 * @param {number} arrEndIndex
 */
const mergeSort = (arr, arrStartIndex, arrEndIndex) => {
  if (arrStartIndex < arrEndIndex) {
    let middleIndex = (arrStartIndex + arrEndIndex) >> 1;

    // 這邊使用 Divide and Conquer，將複雜的問題分成兩個或更多的相同或相似的子問題
    mergeSort(arr, arrStartIndex, middleIndex);
    mergeSort(arr, middleIndex + 1, arrEndIndex);

    merge(arr, arrStartIndex, middleIndex, arrEndIndex);
  }
}

`Java`

class MergeSort {
    void merge(int arr[], int arrStartIndex, int middleIndex, int arrEndIndex) {
        // 計算左右兩陣列的長度
        int leftArrLength = middleIndex - arrStartIndex + 1;
        int rightArrLength = arrEndIndex - middleIndex;

        // 製作左右兩陣列
        int LeftArr[] = new int[leftArrLength];
        int RightArr[] = new int[rightArrLength];

        // 將資料放入左右兩陣列
        for (int i = 0; i < leftArrLength; i++) {
            // 從 arrStarIndex 開始
            LeftArr[i] = arr[arrStartIndex + i];
        }

        for (int j = 0; j < rightArrLength; j++) {
            // 從 middleIndex 開始
            RightArr[j] = arr[middleIndex + 1 + j];
        }

        // 接著要開始遍歷左右陣列準備合併，於是要先建立兩個陣列的 index
        int leftArrIndex = 0, rightArrIndex = 0;
        // 合併後的大陣列 index
        int mergedArrIndex = arrStartIndex;

        while (leftArrIndex < leftArrLength && rightArrIndex < rightArrLength) {
            // 比較左右兩陣列的數值，數值小的放入合併後的陣列
            if (LeftArr[leftArrIndex] <= RightArr[rightArrIndex]) {
                arr[mergedArrIndex] = LeftArr[leftArrIndex];
                leftArrIndex++;
            } else {
                arr[mergedArrIndex] = RightArr[rightArrIndex];
                rightArrIndex++;
            }

            mergedArrIndex++;
        }

        // 將剩餘的數值放入合併後的陣列，剩餘數值會將大於合併後的陣列內的任一元素
        while (leftArrIndex < leftArrLength) {
            arr[mergedArrIndex] = LeftArr[leftArrIndex];
            leftArrIndex++;
            mergedArrIndex++;
        }

        // 將剩餘的數值放入合併後的陣列，剩餘數值會將大於合併後的陣列內的任一元素
        while (rightArrIndex < rightArrLength) {
            arr[mergedArrIndex] = RightArr[rightArrIndex];
            rightArrIndex++;
            mergedArrIndex++;
        }
    }

    void mergeSort(int arr[], int arrStartIndex, int arrEndIndex) {
        if (arrStartIndex < arrEndIndex) {
            int middleIndex = (arrStartIndex + arrEndIndex) / 2;

            // 這邊使用 Divide and Conquer，將複雜的問題分成兩個或更多的相同或相似的子問題
            mergeSort(arr, arrStartIndex, middleIndex);
            mergeSort(arr, middleIndex + 1, arrEndIndex);

            merge(arr, arrStartIndex, middleIndex, arrEndIndex);
        }
    }
}

`C`

#include <stdio.h>

void merge(int arr[], int arrStartIndex, int middleIndex, int arrEndIndex)
{
    int i, j, k;
    // 計算左右兩陣列的長度
    int leftArrLength = middleIndex - arrStartIndex + 1;
    int rightArrLength = arrEndIndex - middleIndex;

    // 製作左右兩陣列
    int LeftArr[leftArrLength], RightArr[rightArrLength];

    // 將資料放入左右兩陣列
    for (i = 0; i < leftArrLength; i++)
    {
        // 從 arrStarIndex 開始
        LeftArr[i] = arr[arrStartIndex + i];
    }

    for (j = 0; j < rightArrLength; j++)
    {
        // 從 middleIndex 開始
        RightArr[j] = arr[middleIndex + 1 + j];
    }

    // 接著要開始遍歷左右陣列準備合併，於是要先建立兩個陣列的 index
    int leftArrIndex = 0;
    int rightArrIndex = 0;
    // 合併後的大陣列 index
    int mergedArrIndex = arrStartIndex;

    while (leftArrIndex < leftArrLength && rightArrIndex < rightArrLength)
    {
        // 比較左右兩陣列的數值，數值小的放入合併後的陣列
        if (LeftArr[leftArrIndex] <= RightArr[rightArrIndex])
        {
            arr[mergedArrIndex] = LeftArr[leftArrIndex];
            leftArrIndex++;
        }
        else
        {
            arr[mergedArrIndex] = RightArr[rightArrIndex];
            rightArrIndex++;
        }

        mergedArrIndex++;
    }

    // 將剩餘的數值放入合併後的陣列，剩餘數值會將大於合併後的陣列內的任一元素
    while (leftArrIndex < leftArrLength)
    {
        arr[mergedArrIndex] = LeftArr[leftArrIndex];
        leftArrIndex++;
        mergedArrIndex++;
    }

    // 將剩餘的數值放入合併後的陣列，剩餘數值會將大於合併後的陣列內的任一元素
    while (rightArrIndex < rightArrLength)
    {
        arr[mergedArrIndex] = RightArr[rightArrIndex];
        rightArrIndex++;
        mergedArrIndex++;
    }
}

void mergeSort(int arr[], int arrStartIndex, int arrEndIndex)
{
    if (arrStartIndex < arrEndIndex)
    {
        int middleIndex = arrStartIndex + (arrEndIndex - arrStartIndex) / 2;

        // 這邊使用 Divide and Conquer，將複雜的問題分成兩個或更多的相同或相似的子問題
        mergeSort(arr, arrStartIndex, middleIndex);
        mergeSort(arr, middleIndex + 1, arrEndIndex);

        merge(arr, arrStartIndex, middleIndex, arrEndIndex);
    }
}

用 `Linked List` 實作

`JS`

class node {
  /**
   * @param {number} val
   * @param {node} next
   */
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

/**
 * @param {node} headRef
 */
const mergeSort = (headRef) => {
  let head = new node();
  let a = new node();
  let b = new node();


  if (head === null || head.next === null) {
    return;
  }

  frontBackSplit(head, a, b);

  mergeSort(a);
  mergeSort(b);

  headRef = sortedMerge(a, b);
}

/**
 * @param {node} a
 * @param {node} b
 */
const sortedMerge = (a, b) => {
  let result = null;

  if (a === null) {
    return b;
  }

  if (b === null) {
    return a;
  }

  if (a.val <= b.val) {
    result = a;
    result.next = sortedMerge(a.next, b);
  } else {
    result = b;
    result.next = sortedMerge(a, b.next);
  }
};

/**
 * @param {node} source
 * @param {node} frontRef
 * @param {node} backRef
 */
const frontBackSplit = (source, frontRef, backRef) => {
  let slow = source, fast = source.next;

  while (fast !== null) {
    fast = fast.next;

    if (fast !== null) {
      slow = slow.next;
      fast = fast.next;
    }
  }

  frontRef = source;
  backRef = slow.next;
  slow.next = null;
};

`Java`

public class MergeSortLinkedList {
    Node head = null;

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
            this.next = null;
        }
    }

    Node sortedMerge(Node a, Node b) {
        Node result = null;

        if (a == null) {
            return b;
        }

        if (b == null) {
            return a;
        }

        if (a.val <= b.val) {
            result = a;
            result.next = sortedMerge(a.next, b);
        } else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }

        return result;
    }

    Node mergeSort(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node middle = getMiddle(head);
        Node nextOfMiddle = middle.next;

        middle.next = null;

        Node left = mergeSort(head);

        Node right = mergeSort(nextOfMiddle);

        Node sortedList = sortedMerge(left, right);
        return sortedList;
    }

    public static Node getMiddle(Node head) {
        if (head == null) {
            return head;
        }

        Node slow = head, fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

`C`

#include <stdio.h>

struct Node
{
    int val;
    struct Node *next;
};

struct Node *SortedMerge(struct Node *a, struct Node *b);
void FrontBackSplit(struct Node *source, struct Node **front_ref, struct Node **back_ref);

// 藉由改變下個節點來排序 Linked List
void MergeSort(struct Node **head_ref)
{
    struct Node *head = *head_ref;
    struct Node *a;
    struct Node *b;

    // 如果節點只有一個或是沒有，那不用排序
    if ((head == NULL) || (head->next == NULL))
    {
        return;
    }

    // 將 List 拆解成兩個子 List： a & b
    FrontBackSplit(head, &a, &b);

    // 對子 List 使用遞迴排序
    MergeSort(&a);
    MergeSort(&b);

    // 將兩個子 List 組合
    *head_ref = SortedMerge(a, b);
}

struct Node *SortedMerge(struct Node *a, struct Node *b)
{
    struct Node *result = NULL;

    // List 為 NULL，不用合併排列
    if (a == NULL)
    {
        return b;
    }

    // List 為 NULL，不用合併排列
    if (b == NULL)
    {
        return a;
    }

    // 比較兩個子 List，較小的元素先放入，然後用遞迴處理
    if (a->val <= b->val)
    {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else
    {
        result = b;
        result->next = SortedMerge(a, b->next);
    }

    return result;
}

// 將 List 拆解成兩個子 List
void FrontBackSplit(struct Node *source, struct Node **front_ref, struct Node **back_ref)
{
    // 使用快慢指標來處理
    struct Node *fast;
    struct Node *slow;
    slow = source;
    fast = source->next;

    // 關鍵，讓 fast 前進兩個節點，slow 前進一個節點
    // 當 slow 走到一半時，fast 肯定在最後，一前一後可以形成兩個長度相似的子 List
    while (fast != NULL)
    {
        fast = fast->next;

        if (fast != NULL)
        {
            slow = slow->next;
            fast = fast->next;
        }
    }

    *front_ref = source;
    *back_ref = slow->next;
    slow->next = NULL;
}

Quick Sort

簡單來說，在數列中隨機選擇一個作為基準，接著剩餘的數與基準比較，放入較大的數列或是較小的數列。完成後，分別對這兩個數列使用相同方法來處理。

用 `Array` 實作

`JS`

/**
 * @param {number[]} arr
 * @param {number} low
 * @param {number} high
 */
const partition = (arr, low, high) => {
  let pivot = arr[high];
  let i = (low - 1);

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  let temp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = temp;
  return (i + 1);
};

/**
 * @param {number[]} arr
 * @param {number} low
 * @param {number} high
 */
const quickSort = (arr, low, high) => {
  if (low < high) {
    let pi = partition(arr, low, high);

    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
};

`Java`

class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return (i + 1);
    }

    void quickSort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
}

`C`

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high)
{
    // 將數列最後一個當作基準
    int pivot = arr[high];
    // i 負責扮演最小元素的 index
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot)
        {
            // 找到最小元素後，先增加 i ，挪到下一個位置，好放置新的最小元素
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int startIndex, int endIndex)
{
    if (startIndex < endIndex)
    {
        int pi = partition(arr, startIndex, endIndex);

        quickSort(arr, startIndex, pi - 1);
        quickSort(arr, pi + 1, endIndex);
    }
}

用 `Linked List` 實作

`JS`

// 才疏學淺，暫時用 class 語法撰寫
class node {
  /**
   * @param {number} val
   * @param {node} next
   */
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class QuickSortLinkedList {
  constructor() {
    this.head = null;
  }

  /**
   * @param {node} start
   * @param {node} end
   */
  partitionLast(start, end) {
    if (start == end || start == null || end == null) {
      return start;
    }

    let pivotPrev = start;
    let current = start;
    let pivot = end.val;

    while (start != end) {
      if (start.val < pivot) {
        pivotPrev = current;
        let temp = current.val;
        current.val = start.val;
        start.val = temp;
        current = current.next;
      }

      start = start.next;
    }

    let temp = current.val;
    current.val = pivot;
    end.val = temp;

    return pivotPrev;
  }

  /**
   * @param {node} start
   * @param {node} end
   */
  quickSort(start, end) {
    if (start == end) {
      return;
    }

    let pivot_prev = this.partitionLast(start, end);
    this.quickSort(start, pivot_prev);

    if (pivot_prev != null && pivot_prev == start) {
      this.quickSort(pivot_prev.next, end);
    } else if (pivot_prev != null && pivot_prev.next != null) {
      this.quickSort(pivot_prev.next.next, end);
    }
  }

  /**
   * @param {number} data
   */
  addNode(data) {
    if (this.head == null) {
      this.head = new node(data);
      return;
    }

    let current = this.head;

    while (current.next != null) {
      current = current.next;
    }

    let newNode = new node(data);
    current.next = newNode;
  }

  /**
   * @param {node} node
   */
  printList(node) {
    let message = '';

    while (node !== null) {
      message += (node.val + ' ');
      node = node.next;
    }

    console.log(message);
  }
}

`Java`

public class QuickSortLinkedList {
    static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
            this.next = null;
        }
    }

    Node head;

    Node partitionLast(Node start, Node end) {
        if (start == end || start == null || end == null) {
            return start;
        }

        Node pivotPrev = start;
        Node current = start;
        int pivot = end.val;

        while (start != end) {
            if (start.val < pivot) {
                pivotPrev = current;
                int temp = current.val;
                current.val = start.val;
                start.val = temp;
                current = current.next;
            }

            start = start.next;
        }

        int temp = current.val;
        current.val = pivot;
        end.val = temp;

        return pivotPrev;
    }

    void sort(Node start, Node end) {
        if (start == end) {
            return;
        }

        Node pivot_prev = partitionLast(start, end);
        sort(start, pivot_prev);

        if (pivot_prev != null && pivot_prev == start) {
            sort(pivot_prev.next, end);
        } else if (pivot_prev != null && pivot_prev.next != null) {
            sort(pivot_prev.next.next, end);
        }
    }
}

`C`

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node *next;
};

struct Node *getTail(struct Node *cur)
{
    while (cur != NULL && cur->next != NULL)
    {
        cur = cur->next;
    }

    return cur;
}

struct Node *partition(struct Node *head, struct Node *end,
                       struct Node **newHead, struct Node **newEnd)
{
    struct Node *pivot = end;
    struct Node *prev = NULL;
    struct Node *cur = head;
    struct Node *tail = pivot;

    while (cur != pivot)
    {
        if (cur->data < pivot->data)
        {
            if ((*newHead) == NULL) {
                (*newHead) = cur;
            }

            prev = cur;
            cur = cur->next;
        }
        else
        {
            if (prev) {
                prev->next = cur->next;
            }

            struct Node *tmp = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }

    if ((*newHead) == NULL) {
        (*newHead) = pivot;
    }

    (*newEnd) = tail;

    return pivot;
}

struct Node *quickSortRecur(struct Node *head, struct Node *end)
{
    if (!head || head == end)
    {
        return head;
    }

    struct Node *newHead = NULL;
    struct Node *newEnd = NULL;

    struct Node *pivot = partition(head, end, &newHead, &newEnd);

    if (newHead != pivot)
    {

        struct Node *tmp = newHead;

        while (tmp->next != pivot) {
            tmp = tmp->next;
        }

        tmp->next = NULL;

        newHead = quickSortRecur(newHead, tmp);

        tmp = getTail(newHead);
        tmp->next = pivot;
    }

    pivot->next = quickSortRecur(pivot->next, newEnd);

    return newHead;
}

void quickSort(struct Node **headRef)
{
    (*headRef) = quickSortRecur(*headRef, getTail(*headRef));
    return;
}

刷題

跟前兩天一樣先跳過，之後介紹完 Sort 之後，會花一天時間，同一題用不同 Sort 來處理。

結論

時間複雜度的部分：

Merge Sort 切成小數列要花費 O(log n)，合併時花費 O(n)，所以耗費 O(n log n)。
Quick Sort 如同 Merge Sort，切出小數列要花費 O(log n)，比較合併時花費 O(n)，所以耗費 O(n log n)。

六種 Sort 告一段落，明天來刷題。

Day 08: Sort(2) - Insertion Sort & Heap Sort

Day 10: Sort(4) - 演算法練習

系列文

你總是躲不掉的，不如放膽面對 LeetCode 吧！共 31 篇

目錄

RSS系列文訂閱系列文

66 人訂閱

完整目錄

直播研討會

{{ item.subject }}

{{ item.channelVendor }} {{ item.webinarstarted }} |

{{ formatDate(item.duration) }}

直播中

尚未有邦友留言

立即登入留言

參賽組數

1064 組

團體組數

40 組

累計文章數

22198 篇

完賽人數

602 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js

IT邦幫忙